package model.algorithms.linksMapping;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map.Entry;

import model.components.links.link.Link;
import model.components.networks.sdn.SdnNetwork;
import model.components.networks.virtual.VirtualNetwork;
import model.components.nodes.node.sdn.SdnNode;
import model.components.nodes.node.virtual.VirtualNode;

public class ShortestPath extends LinksMappingAlgorithm
{
	public ShortestPath( String name )
	{
		super( name );
	}
	
	protected int[][][] linksMapping( VirtualNetwork virtualNetwork, SdnNetwork sdnNetwork, LinkedHashMap< VirtualNode, SdnNode > nodesMapping, double availableBWsIn[][] )
	{
		int linksMapping[][][] = new int[ virtualNetwork.getLinks().size() ][ sdnNetwork.getNodes().size() ][ sdnNetwork.getNodes().size() ];
		boolean isLinksMapping = true;
		
		List< Link > virtualLinks = virtualNetwork.getLinks();
		int sdnNodesNumber = sdnNetwork.getNodes().size();
		
		double availableBWs[][] = new double[ sdnNodesNumber ][ sdnNodesNumber ];
		double availableBWsCostMetric[][] = new double[ sdnNodesNumber ][ sdnNodesNumber ];
		
		for( int i = 0; i < sdnNetwork.getNodes().size(); i++ )
			for( int j = 0; j < sdnNetwork.getNodes().size(); j++ )
			{
				availableBWs[ i ][ j ] = availableBWsIn[ i ][ j ];
				availableBWsCostMetric[ i ][ j ] = availableBWsIn[ i ][ j ];
			}
		
		for( int i = 0; i < sdnNodesNumber; i++ )
			for( int j = 0; j < sdnNodesNumber; j++ )
				if( availableBWsCostMetric[ i ][ j ] != 0 )
					availableBWsCostMetric[ i ][ j ] = 1 / availableBWsCostMetric[ i ][ j ];
		
		for( Link virtualLink: virtualLinks )
		{
			int firstSubstrateNodeNumber = 0;
			int secondSubstrateNodeNumber = 0;
			
			Iterator< Entry< VirtualNode, SdnNode > > iterator = nodesMapping.entrySet().iterator();
		    
		    while( iterator.hasNext() )
		    {
		    	boolean isFirstSubstrateNodeNumber = false;
		    	boolean isSecondSubstrateNodeNumber = false;
		    	
		    	Entry< VirtualNode, SdnNode > nodeMapping = iterator.next();
		    	
		    	if( virtualLink.getFirstNode().getNumber() == nodeMapping.getKey().getNumber() )
		    	{
		    		isFirstSubstrateNodeNumber = true;
		    		firstSubstrateNodeNumber = nodeMapping.getValue().getNumber();
		    	}
		    	
		    	if( virtualLink.getSecondNode().getNumber() == nodeMapping.getKey().getNumber() )
		    	{
		    		isSecondSubstrateNodeNumber = true;
		    		secondSubstrateNodeNumber = nodeMapping.getValue().getNumber();
		    	}
		    	
		    	if( isFirstSubstrateNodeNumber && isSecondSubstrateNodeNumber )
		    		break;
		    }
		    
		    double bandwidthCostMetric = 1 / virtualLink.getBW();
		    
			int previousSubstrateNodeNumber[] = null;
					
			if( this.getCostMetric().equals( DISTANCE_COST ) )
				previousSubstrateNodeNumber = this.shortestDistanceNodesNumbers( sdnNetwork, firstSubstrateNodeNumber, availableBWs, virtualLink.getBW() );
			
			else if( this.getCostMetric().equals( BW_COST ) )
				previousSubstrateNodeNumber = this.higherAvailableBandwidthNodesNumbers( sdnNetwork, firstSubstrateNodeNumber, availableBWsCostMetric, bandwidthCostMetric );
			
			List< Integer > shortPath = new ArrayList< Integer >();
			
			if( previousSubstrateNodeNumber == null )
			{
				isLinksMapping = false;
				
				break;
			}
			else
				shortPath = this.shortPath( previousSubstrateNodeNumber, firstSubstrateNodeNumber, secondSubstrateNodeNumber );
			
			if( shortPath.get( shortPath.size() - 1 ) != secondSubstrateNodeNumber )
			{
				isLinksMapping = false;
				
				break;
			}

			for( int i = 0; i < shortPath.size() - 1; i++ )
			{
				int substrateNodeNumber = shortPath.get( i );
				int nextSubstrateNodeNumber = shortPath.get( i + 1 );
				
				linksMapping[ virtualLink.getNumber() ][ substrateNodeNumber ][ nextSubstrateNodeNumber ] = virtualLink.getBW();
				
				availableBWsCostMetric[ substrateNodeNumber ][ nextSubstrateNodeNumber ] = 1 / availableBWsCostMetric[ substrateNodeNumber ][ nextSubstrateNodeNumber ] - 1 / Math.abs( bandwidthCostMetric );
				availableBWsCostMetric[ substrateNodeNumber ][ nextSubstrateNodeNumber ] = 1 / availableBWsCostMetric[ substrateNodeNumber ][ nextSubstrateNodeNumber ];
				availableBWsCostMetric[ nextSubstrateNodeNumber ][ substrateNodeNumber ] = availableBWsCostMetric[ substrateNodeNumber ][ nextSubstrateNodeNumber ];
				
			    availableBWs[ substrateNodeNumber ][ nextSubstrateNodeNumber ] -= virtualLink.getBW();
				availableBWs[ nextSubstrateNodeNumber ][ substrateNodeNumber ] = availableBWs[ substrateNodeNumber ][ nextSubstrateNodeNumber ];
			}
		}
		
		if( isLinksMapping == false )
			linksMapping = null;
		
		return linksMapping;
	}
	
	private List< Integer > shortPath( int previousNodesNumbers[], int firstNodeNumber, int secondNodeNumber )
	{
		List< Integer > shortPath = new ArrayList< Integer >();
		int previousSecondNodeNumber = secondNodeNumber;
		
		while( previousSecondNodeNumber != firstNodeNumber && previousSecondNodeNumber > -1 )
		{
			shortPath.add( 0, previousSecondNodeNumber );
			previousSecondNodeNumber = previousNodesNumbers[ previousSecondNodeNumber ];
		}
		
		shortPath.add( 0, firstNodeNumber );
		
		return shortPath;
	}
	
	private int[] higherAvailableBandwidthNodesNumbers( SdnNetwork substrateNetwork, int firstNodeNumber, double availableBandwidthsCostMetric[][], double bandwidthCostMetric )
	{	
		int nodesNumber = substrateNetwork.getNodes().size();
		double shortestDistances[] = new double[ nodesNumber ];
			 
		for( int i = 0; i < shortestDistances.length; i++ )
			shortestDistances[ i ] = Integer.MAX_VALUE;
		 
		shortestDistances[ firstNodeNumber ] = 0;
		
		boolean areVisitedNodes[] = new boolean[ nodesNumber ];
		int shortestDistanceNodesNumbers[] = new int[ nodesNumber ];
		
		for( int i = 0; i < shortestDistances.length; i++ )
		{
			int shortestDistanceNodeNumber = this.shortestDistanceNodeNumber( shortestDistances, areVisitedNodes );
		
			if( shortestDistanceNodeNumber == -1 )
				break;
			
			areVisitedNodes[ shortestDistanceNodeNumber ] = true;
		 
			List< Integer > neighbourNodesNumbers = new ArrayList< Integer >();
			 
			for( int j = 0; j < nodesNumber; j++ )
				if( availableBandwidthsCostMetric[ shortestDistanceNodeNumber ][ j ] != 0 )
					if( availableBandwidthsCostMetric[ shortestDistanceNodeNumber ][ j ] < Math.abs( bandwidthCostMetric ) )
						neighbourNodesNumbers.add( j );
			 
			for( int j = 0; j < neighbourNodesNumbers.size(); j++ )
			{
				int neighbourNodeNumber = neighbourNodesNumbers.get( j );
				double shortestDistance = shortestDistances[ shortestDistanceNodeNumber ] + availableBandwidthsCostMetric[ shortestDistanceNodeNumber ][ neighbourNodeNumber ];
				 
				if( shortestDistance < shortestDistances[ neighbourNodeNumber ] )
				{
					shortestDistances[ neighbourNodeNumber ] = shortestDistance;
					shortestDistanceNodesNumbers[ neighbourNodeNumber ] = shortestDistanceNodeNumber;
				}
			}
		}
	
		return shortestDistanceNodesNumbers;
	}
	
	private int[] shortestDistanceNodesNumbers( SdnNetwork substrateNetwork, int firstNodeNumber, double availableBandwidths[][], double bandwidth )
	{	
		int nodesNumber = substrateNetwork.getNodes().size();
		double distances[][] = this.distances( substrateNetwork );
		double shortestDistances[] = new double[ nodesNumber ];
			 
		for( int i = 0; i < shortestDistances.length; i++ )
			shortestDistances[ i ] = Integer.MAX_VALUE;
		
		shortestDistances[ firstNodeNumber ] = 0;
		
		boolean areVisitedNodes[] = new boolean[ nodesNumber ];
		
		int shortestDistanceNodesNumbers[] = new int[ nodesNumber ];
		
		for( int i = 0; i < nodesNumber; i++ )
			shortestDistanceNodesNumbers[ i ] = -1;
		
		for( int i = 0; i < shortestDistances.length; i++ )
		{
			int shortestDistanceNodeNumber = this.shortestDistanceNodeNumber( shortestDistances, areVisitedNodes );
		
			if( shortestDistanceNodeNumber == -1 )
				break;
			
			areVisitedNodes[ shortestDistanceNodeNumber ] = true;
		 
			List< Integer > neighbourNodesNumbers = new ArrayList< Integer >();
			 
			for( int j = 0; j < nodesNumber; j++ )
				if( availableBandwidths[ shortestDistanceNodeNumber ][ j ] != 0 )
					if( bandwidth < availableBandwidths[ shortestDistanceNodeNumber ][ j ] )
						neighbourNodesNumbers.add( j );
			 
			for( int j = 0; j < neighbourNodesNumbers.size(); j++ )
			{
				int neighbourNodeNumber = neighbourNodesNumbers.get( j );
				double shortestDistance = shortestDistances[ shortestDistanceNodeNumber ] + distances[ shortestDistanceNodeNumber ][ neighbourNodeNumber ];
				 
				if( shortestDistance < shortestDistances[ neighbourNodeNumber ] )
				{
					shortestDistances[ neighbourNodeNumber ] = shortestDistance;
					shortestDistanceNodesNumbers[ neighbourNodeNumber ] = shortestDistanceNodeNumber;
				}
			}
		}
		
		for( int i = 0; i < nodesNumber; i++ )
			if( shortestDistanceNodesNumbers[ i ] != -1 )
				return shortestDistanceNodesNumbers;
		
		return null;
	}
	
	private int shortestDistanceNodeNumber( double shortestDistances[], boolean areVisitedNodes[] )
	{
		double shortestDistance = Integer.MAX_VALUE;
		int shortDistanceNodeNumber = -1;
		
		for( int i = 0; i < shortestDistances.length; i++ )
			if( !areVisitedNodes[ i ] && shortestDistances[ i ] < shortestDistance )
			{
				shortestDistance = shortestDistances[ i ];
				shortDistanceNodeNumber = i;
			}
		
		return shortDistanceNodeNumber;
	}
	
}
